#ifdef WIN32
#include "windows.h"
#else
#include <sys/time.h>
#include <time.h>
#endif
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "stdarg.h"
#include "math.h"

#include "BList.h"

#include "symbol.h"
#include "sort.h"
#include "ontology.h"
#include "featureterm.h"
#include "FTKBase.h"
#include "AUfeatureterm.h"
#include "FT_refinement.h"
#include "FT_generalization.h"

#include "entropy.h"



FeatureTerm *refinement_LID(FeatureTerm *problem,List<FeatureTerm> *cases,Path *description_path,Path *solution_path,Ontology *o,FTKBase *domain_model,int heuristic,int selection_mode,int min_precedents)
{
	List<FeatureTerm> *discriminant_set,*dset_tmp;
	List<FeatureTerm> *discriminant_solutions,*dsolutions_tmp;
	List<FeatureTerm> solutions;
	FeatureTerm *description,*solution,*final_solution;
	FeatureTerm *last_description,*current_description,*refinement;
	List<FeatureTerm> *description_refinements;
	List<FeatureTerm> objects;
	int nrefinements,i,selected;
	float *heuristics;
	int *coverage;
	bool finished;

	/* Create the initial description and discriminant sets: */ 
	objects.Add(new FeatureTerm(problem));
	current_description = new FeatureTerm((Symbol *)0,o->get_sort("any"),0);
	{
		List<FeatureTerm> l;
		List<FeatureTerm> *l1,*l2;
		FeatureTerm *c;

		discriminant_set=new List<FeatureTerm>;
		discriminant_solutions=new List<FeatureTerm>;

		l.Instance(*cases);
		l.Rewind();
		while(l.Iterate(c)) {
			l1=c->readPath(description_path);
			l2=c->readPath(solution_path);
			if (l1->Length()==1 && l2->Length()==1) {
				discriminant_set->Add(l1->ExtractIni());
				discriminant_solutions->Add(l2->ExtractIni());
			} /* if */ 
			delete l1;
			delete l2;
		} /* while */ 

//		printf("rLID: %i initial cases\n",discriminant_set->Length());
	}

	/* Compute the different solutions: */ 
	{
		List<FeatureTerm> l;

//		printf("Solutions:\n");
		l.Instance(*discriminant_solutions);
		while(l.Iterate(solution)) {
			if (!solutions.MemberP(solution)) {
				solutions.Add(new FeatureTerm(solution));
/*				
				{
					char *s;
					s=solution->toNiceString();
					printf("%s\n",s);
					delete []s;
				}
*/
			} /* if */ 
		} /* while */ 
	}

	if (solutions.Length()==0) {
		printf("rLID: ERROR!! no solutions!\n");
		delete current_description;
		delete discriminant_set;
		delete discriminant_solutions;
		return 0;
	} /* if */ 

	do{

		{
			char *s;
			FeatureTerm *sol,*sol2;
			List<FeatureTerm> l,l2;
			int count;

			s=current_description->toStringNOOS(domain_model);
			printf("Justification:\n%s\n",s);
			delete []s;
			printf("Precedents: %i\n",discriminant_set->Length());

			l.Instance(solutions);
			l2.Instance(*discriminant_solutions);
			while(l.Iterate(sol)) {
				count=0;
				l2.Rewind();
				while(l2.Iterate(sol2)) if (*sol==*sol2) count++;

				s=sol->getName()->get();
				printf("%s - %i | ",s,count);

			} // while  
			printf("\n");
		}

		finished=false;
		description_refinements = DSpecializationL2(current_description,&objects,0,o,-1,domain_model);
		
		//		printf("\nrLID: %i refinements\n",description_refinements->Length());
		/* Filter refinements: */ 
		{
			List<FeatureTerm> to_delete;
			bool valid;

			description_refinements->Rewind();
			while(description_refinements->Iterate(refinement)) {
				valid=false;

				if (refinement->subsumes(problem) && !refinement->subsumes(current_description)) {
					valid=true;
//					discriminant_set->Rewind();
//					while(!valid && discriminant_set->Iterate(description)) 
//						if (refinement->subsumes(description)) valid=true;
				} /* if */ 

				if (!valid) to_delete.Add(refinement);
			} /* while */ 

			while(!to_delete.EmptyP()) {
				refinement=to_delete.ExtractIni();
				description_refinements->DeleteElement(refinement);
				delete refinement;
			} /* while */ 
		}
//		printf("rLID: %i valid refinements\n",description_refinements->Length());
		
		selected=-1;
		if (description_refinements->Length()>0) {

			/* Evaluate all the refinements: */ 
			nrefinements=description_refinements->Length();
			heuristics=new float[nrefinements];
			coverage=new int[nrefinements];
			description_refinements->Rewind();
			i=0;
//			printf("Heuristics:\n");
			while(description_refinements->Iterate(refinement)) {
				switch(heuristic) {
				case 0:	/* Information Gain: */ 
						heuristics[i]=h_information_gain(discriminant_set,discriminant_solutions,&solutions,refinement,&(coverage[i]));
						break;
				case 1: /* RLDM: */ 
						heuristics[i]=1-h_rldm(discriminant_set,discriminant_solutions,&solutions,refinement,&(coverage[i]));
						break;
				case 2: /* Entropy: */ 
						heuristics[i]=h_entropy(discriminant_set,discriminant_solutions,&solutions,refinement,&(coverage[i]));
						break;
				default:coverage[i]=0;
						heuristics[i]=0;
						break;
				} /* switch */ 	
				
//				printf("%g [%i]\n",heuristics[i],coverage[i]);

				i++;
			} /* while */ 

			/* Choose one refinement: */ 
			switch(selection_mode) {
				case 0:/* MAXIMUM: */ 
					{
						int i;
						float maximum=heuristics[0];
						selected=0;

						for(i=1;i<nrefinements;i++) {
							if (heuristics[i]>maximum || (heuristics[i]==maximum && coverage[i]>coverage[selected])) {
								maximum=heuristics[i];
								selected=i;
							} /* if */ 
						} /* for */  
					}
					break;
				case 1:/* RANDOM: */ 
					selected=rand()%nrefinements;
					break;
				case 2:/* RANDOM PONDERATED: */ 
					{
						int i;
						float h_sum=0;
						float tmp,accum;

//						printf("{ 0");
						for(i=0;i<nrefinements;i++) {
							h_sum+=heuristics[i];
//							printf(" - %g",h_sum);
						} /* if */ 
						tmp=(float(rand())*h_sum)/float(RAND_MAX);

						selected=-1;
						accum=0;
						for(i=0;selected==-1 && i<nrefinements;i++) {
							if (accum+heuristics[i]>tmp) selected=i;
							accum+=heuristics[i];
						} /* for */ 

//						printf(" } -> %g -> %i\n",tmp,selected);

						if (selected==-1) selected=rand()%nrefinements;
					}
					break;
				case 3:/* MINIMUM: */ 
					{
						int i;
						float minimum=heuristics[0];
						selected=0;

						for(i=1;i<nrefinements;i++) {
							if (heuristics[i]<minimum || (heuristics[i]==minimum && coverage[i]>coverage[selected])) {
								minimum=heuristics[i];
								selected=i;
							} /* if */ 
						} /* for */  
					}
					break;

				default:
					selected=0;
					break;
			} /* while */ 

			delete []heuristics;
			delete []coverage;
		} /* if */ 

		if (selected>=0) {
//			printf("rLID: selected refinement %i\n",selected);

			last_description=current_description;
			current_description=new FeatureTerm(description_refinements->operator [](selected));
/*
			{
				char *s;
				s=current_description->toStringNOOS(domain_model);
				printf("%s\n",s);
				delete []s;
			}
*/

			dset_tmp=new List<FeatureTerm>;
			dsolutions_tmp=new List<FeatureTerm>;

			discriminant_set->Rewind();
			discriminant_solutions->Rewind();
			while(discriminant_set->Iterate(description) &&
				  discriminant_solutions->Iterate(solution)) {
				if (current_description->subsumes(description)) {
					dset_tmp->Add(new FeatureTerm(description));
					dsolutions_tmp->Add(new FeatureTerm(solution));
				} /* if */ 
			} /* while */ 

//			printf("rLID: |Dset| = %i\n",dset_tmp->Length());

			if (dset_tmp->Length()>0) {
				delete last_description;
				delete discriminant_set;
				delete discriminant_solutions;
				discriminant_set=dset_tmp;
				discriminant_solutions=dsolutions_tmp;
				dset_tmp=0;
				dsolutions_tmp=0;
			} else {
				delete current_description;
				current_description=last_description;
				delete dset_tmp;
				delete dsolutions_tmp;
				dset_tmp=0;
				dsolutions_tmp=0;

				selected=-1;	/* Don't select this refinement, since it makes de discriminant set to be empty */ 
			} /* if */ 
		} /* if */ 

		delete description_refinements;

		if (selected>=0) {
			List<FeatureTerm> l,stmp;

//			printf("Candidate solutions: ");
			l.Instance(*discriminant_solutions);
			while(l.Iterate(solution)) {
				if (!stmp.MemberP(solution)) {
					stmp.Add(new FeatureTerm(solution));
/*
					{
						char *s;
						s=solution->toNiceString();
						printf("%s ",s);
						delete []s;
					}
*/
				} /* if */ 
			} /* while */ 
//			printf("\n");

			if (stmp.Length()==1) finished=true;
		} /* if */ 

		if (discriminant_set->Length()<min_precedents) finished=true;

	}while(selected>=0 && !finished);

	/* Determine final solution: */ 
	{
		List<FeatureTerm> l;
		int *distribution=new int[solutions.Length()];
		int maximum,selected,i;

		for(i=0;i<solutions.Length();i++) distribution[i]=0;

		l.Instance(*discriminant_solutions);
		while(l.Iterate(solution)) {
			distribution[solutions.Position(solution)]++;
		} /* while */ 

		maximum=distribution[0];
		selected=0;

		for(i=0;i<solutions.Length();i++) {
			if (distribution[i]>maximum) {
				maximum=distribution[i];
				selected=i;
			} /* if */ 
		} /* for */ 

		final_solution=new FeatureTerm(solutions[selected]);
	} /* if */ 

	/* Show result: */ 
	{
		char *s;
		printf("/- rLID ---------------------------------------------------------\\\n");
		printf("* Problem:\n");
		s=problem->getName()->get();
		printf("  %s\n",s);		
		printf("* Solution:\n");
		s=final_solution->toStringNOOS();
		printf("  %s\n",s);
		delete []s;
		printf("* Justification:\n");
		s=current_description->toStringNOOS(domain_model);
		printf("%s\n",s);
		delete []s;
		printf("* Discriminant set:\n");
		{
			discriminant_set->Rewind();
			discriminant_solutions->Rewind();
			while(discriminant_set->Iterate(description) &&
				  discriminant_solutions->Iterate(solution)) {
				s=description->getName()->get();
				printf("  %s -> ",s);				
				s=solution->toStringNOOS();
				printf("%s\n",s);
				delete []s;
			} /* while */ 
		}
		printf("\\----------------------------------------------------------------/\n");
	}

	delete current_description;
	delete discriminant_set;
	delete discriminant_solutions;

	return final_solution;
} /* refinement_LID */ 


